#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 50005
int M;
int map[305][305], safe[305][305], vis[305][305];
struct pos
{
    int x, y, t;
    pos(int x = 0, int y = 0, int t = 0) : x(x), y(y), t(t){};
    bool operator<(pos p) { return t < p.t; }
};
queue<pos> qu;
int X, Y, T;
int main()
{
    cin >> M;
    fill(map[0], map[0] + 305 * 305, 0x3fffffff);
    for (int i = 0; i < M; ++i)
    {
        cin >> X >> Y >> T;
        map[X][Y] = min(T, map[X][Y]), safe[X][Y] = 1; //中
        if (X <= 300)
            map[X + 1][Y] = min(T, map[X + 1][Y]), safe[X + 1][Y] = 1; //右
        if (Y <= 300)
            map[X][Y + 1] = min(T, map[X][Y + 1]), safe[X][Y + 1] = 1; //上
        if (Y >= 1)
            map[X][Y - 1] = min(T, map[X][Y - 1]), safe[X][Y - 1] = 1; //下
        if (X >= 1)
            map[X - 1][Y] = min(T, map[X - 1][Y]), safe[X - 1][Y] = 1; //左
    }
    pos now = pos(0, 0, 0); //开始的时候Becy在原点
    qu.push(now);
    while (!qu.empty())
    {
        now = qu.front();
        qu.pop();
        X = now.x, Y = now.y, T = now.t;
        if (safe[X][Y] == 0)
            break;
        if (map[X][Y] <= T || vis[X][Y] == 1) //t时刻该点被摧毁或已经访问过
        {
            T = -1;
            continue;
        }
        vis[X][Y] = 1;
        if (X <= 300)
            qu.push(pos(X + 1, Y, T + 1)); //向右走
        if (Y <= 300)
            qu.push(pos(X, Y + 1, T + 1)); //向上走
        if (Y >= 1)
            qu.push(pos(X, Y - 1, T + 1)); //向下走
        if (X >= 1)
            qu.push(pos(X - 1, Y, T + 1)); //向左走
    }
    cout << T << endl;
    return 0;
}